class Solution:
    def maxSubArray(self, nums):
        def divide_and_conquer(left, right):
            # 基本情况：子数组只有一个元素
            if left == right:
                return nums[left]

            mid = (left + right) // 2

            # 递归求解左半部分的最大子数组和
            left_max = divide_and_conquer(left, mid)
            # 递归求解右半部分的最大子数组和
            right_max = divide_and_conquer(mid + 1, right)

            # 计算跨越中间的最大子数组和
            # 从中间向左扩展，求最大左半部分和
            left_sum = -float("inf")
            current_sum = 0
            for i in range(mid, left - 1, -1):
                current_sum += nums[i]
                left_sum = max(left_sum, current_sum)

            # 从中间向右扩展，求最大右半部分和
            right_sum = -float("inf")
            current_sum = 0
            for i in range(mid + 1, right + 1):
                current_sum += nums[i]
                right_sum = max(right_sum, current_sum)

            # 跨越中间的最大子数组和
            cross_max = left_sum + right_sum

            # 返回左、右、跨越三者的最大值
            return max(left_max, right_max, cross_max)

        return divide_and_conquer(0, len(nums) - 1)
